/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
    let stack1=[root];
    let stack2=[root];
    function search(target,node,route){
        if(node.val==target){
            return true;
        }
        if(node.left){
            route.push(node.left);
            if(search(target,node.left,route)){
                return true;
            }
            route.pop();
        }
        if(node.right){
            route.push(node.right);
            if(search(target,node.right,route)){
                return true;
            }
            route.pop(); 
        }
        return false;
    }
    search(p.val,root,stack1);
    search(q.val,root,stack2);                          
    for(var i=0;i<Math.min(stack1.length,stack2.length);i++){
        if(stack1[i].val!=stack2[i].val){
            break;
        }
    }
    return stack1[i-1];
};


